/**
 * @Author：ming
 * @Date：2023/9/26 11:03 AM
 * @Filename：Lc15
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author ming
 */
public class Lc15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < len-2; i++) {
            if(nums[i]>0){
                break;
            }

            if(i>0 && nums[i]==nums[i-1]) continue;

            int l =i+1;
            int r = len-1;
            int a = -1;
            while (l<r){
                a = nums[i]+nums[l]+nums[r];
                if(a==0){
                    ArrayList<Integer> list = new ArrayList<>(Arrays.asList(nums[i], nums[l], nums[r]));
                    lists.add(list);
                    while (l<r&&nums[r]==nums[--r]);
                    while (l<r&&nums[l]==nums[++l]);
                }else if(a>0){
                    while (l<r&&nums[r]==nums[--r]);
                }else {
                    while (l<r&&nums[l]==nums[++l]);
                }
            }
        }
        return lists;
    }
}
